Caching is a well-known technique that uses a smaller, faster storage device to speed up access to data stored in a larger, slower storage device. A typical application of caching is found in disk access technology. A processor based system accessing data on a hard disk drive, for example, may achieve improved performance if a cache implemented in solid state memory that has a lower access time than the drive is interposed between the drive and the processor. As is well known to those skilled in the art, such a cache is populated by data from the disk that is accessed by the system and subsequent accesses to the same data can then be made to the cache instead of to the disk, thereby speeding up performance. The use of caching imposes certain constraints on the design of a system, such as a requirement of cache consistency with the main storage device, e.g. when data is written to the cache, as well as performance based constraints which dictate, e.g. what parts of the cache are to be replaced when a data access is made to a data element that is not in the cache and the cache happens to be full (cache replacement policy).
A well known design for caches, specifically for disk caches, is an N-way set associative cache, where N is some non-zero whole number. In such a design, the cache may be implemented as a collection of N arrays of cache lines, each array representing a set, each set in turn having as members only such data elements, or, simply, elements, from the disk whose addresses map to a set based on an easily computed mapping function. Thus, in the case of a disk cache, any element on a disk can be quickly mapped to a set in the cache by, for example, obtaining the integer value resulting from performing a modulus of the address of the element on disk, that is, its tag, with the number of sets, N, in the cache (the tag MOD N) the result being a number that uniquely maps the element to a set. Many other methods may be employed to map a line to a set in a cache, including bit shifting of the tag, or any other unique set of bits associated with the line, to obtain an index for a set; performing a logical AND between the tag or other unique identifier and a mask; XOR-ing the tag or other unique identifier with a mask to derive a set number, among others well known to those skilled in the art, and the claimed subject matter is not limited to any one or more of these methods.
To locate an element in a set associative cache, the system uses the address of the data on the disk to compute the set in which the element would reside, and then in a typical implementation searches through the array representing the set until a match is found, or it is determined that the element is not in the set.
A similar implementation of a cache may use a hash table instead of associative sets to organize a cache. In such a cache, once again, elements are organized into fixed size arrays, usually of equal sizes. However, in this instance, a hashing function is used to compute the array (termed a hash bucket) within which an element is located. The input to the hashing function may be based on the element's tag and the function then maps the element to a particular hash bucket. Hashing functions and their uses for accessing data and cache organization are well known and are not discussed here in detail.
To simplify the exposition of the subject matter in this application, the term Constant Access Time Bounded (CATB) is introduced to describe cache designs including the set associative and hash table based caches described above. A key feature of CATB caches in the art is that they are organized into fixed sized arrays, generally of equal size, each of which is addressable in constant time based on some unique aspect of a cache element such as its tag. Other designs for CATB caches may be readily apparent to one skilled in the art. In general the access time to locate an element in a CATB cache is bounded by a constant, or at least is independent of the total cache size, because the time to identify an array is constant and each array is of a fixed size, and so searching within the array is bounded by a constant. For uniformity of terminology, the term search group is used to refer to the array (i.e. the set in a set associative cache or the hash bucket in the hash table based cache) that is identified by mapping an element.
Each element in a CATB cache, or cache line, contains both the actual data from the slower storage device that is being accessed by the system as well as some other data termed metadata that is used by the cache management system for administrative purposes. The metadata may include a tag i.e. the unique identifier or address for the data in the line, and other data relating to the state of the line including a bit or flag to indicate if the line is in use (allocated) or not in use (unallocated), as well as bits reserved for other purposes.
Typically, caches are used for both reading and writing data. Generally there are two types of policies that caches may use for writing data to a location that is in the cache. One is termed a write through policy and the other a write-back policy. In a write through cache, data modified at a location that is in a cache is also immediately written to the main storage device, such as a disk. This ensures consistency between the main storage device and the cache, but may impose a performance penalty, because writing to the main storage device is usually significantly slower than writing to the cache. A write-back cache, however, does not immediately write data that is modified in the cache back to the main storage device. Rather, the cache management system waits until an appropriate time to write the data back to the main storage device, such as when the system is idle. During the time between the modification of data in the cache and time the data is written back to main storage, the cache line with the modified data is not consistent with the corresponding location in main storage and is said to be dirty.
A problem arises when in the course of the operation of the cache, a cache line that the cache replacement policy chooses for eviction from the cache also happens to be dirty. After the data in the cache line is evicted, in a typical cache, the cache line is overwritten by new data. To ensure consistency with main storage, therefore, the modified data in the dirty cache line chosen for eviction may have to be written back to main storage before the line can be evicted. This generally produces an undesirable performance penalty for the system at a time when the system is not idling. Alternatively, in systems where power consumption is an issue, a write-back may cause additional power consumption if a disk drive needs to be spun up from a low power consuming state in order to accomplish the write to the disk. This problem is termed the dirty evict problem.